class Solution {
public:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    void solve(vector<vector<char>>& b) {
        int m=b.size();
        int n=b[0].size();
        for(int i=0;i<m;++i)
        {
            if(b[i][0]=='O')
                bfs(b,i,0,m,n,'1','O');
            if(b[i][n-1]=='O')
                bfs(b,i,n-1,m,n,'1','O');
        }
        for(int i=0;i<n;++i)
        {
            if(b[0][i]=='O')
                bfs(b,0,i,m,n,'1','O');
            if(b[m-1][i]=='O')
                bfs(b,m-1,i,m,n,'1','O');
        }


        for(int i=0;i<m;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(b[i][j]=='O')
                    bfs(b,i,j,m,n,'X','O');
            }
        }


        for(int i=0;i<m;++i)
        {
            if(b[i][0]=='1')
                bfs(b,i,0,m,n,'O','1');
            if(b[i][n-1]=='1')
                bfs(b,i,n-1,m,n,'O','1');
        }
        for(int i=0;i<n;++i)
        {
            if(b[0][i]=='1')
                bfs(b,0,i,m,n,'O','1');
            if(b[m-1][i]=='1')
                bfs(b,m-1,i,m,n,'O','1');
        }
    }
    void bfs(vector<vector<char>>& b,int x,int y,
    int m,int n,char mynew,char myold)
    {
        queue<pair<int,int>> q;
        q.push({x,y});
        b[x][y]=mynew;
        while(q.size())
        {
            auto [x1,y1]=q.front();
            q.pop();
            for(int i=0;i<4;++i)
            {
                int x2=x1+dx[i];
                int y2=y1+dy[i];
                if(x2>=0&&x2<m&&y2>=0&&y2<n&&b[x2][y2]==myold)
                {
                    q.push({x2,y2});
                    b[x2][y2]=mynew;
                }
            }
        }
    }
};
